class Area:
    def __init__(self,nw,ne,se,sw,parent):
        self.points = {'nw':nw, 'ne':ne, 'se':se, 'sw':sw}
        self.parent = parent
        self.split = None
        self.subArea = {'nw':None, 'ne':None, 'se':None, 'sw':None}
    
    def getArea(self,point):
        if self.split == None:
            return [self]
        else:
            if point.x == self.split.x:
               if point.y == self.split.y:
                    return []
                elif point.y > self.split.y:
                    return self.subArea['se'].getArea(point) + self.subArea['sw'].getArea(point)
                else:
                    return self.subArea['ne'].getArea(point) + self.subArea['nw'].getArea(point)
            elif point.x > self.split.x:
                if point.y == self.split.y:
                    return self.subArea['se'].getArea(point) + self.subArea['ne'].getArea(point)
                elif point.y > self.split.y:
                    return self.subArea['se'].getArea(point)
                else:
                    return self.subArea['ne'].getArea(point)
            else:
                if point.y == self.split.y:
                    return self.subArea['sw'].getArea(point) + self.subArea['nw'].getArea(point)
                if point.y > self.split.y:
                    return self.subArea['sw'].getArea(point)
                else:
                    return self.subArea['nw'].getArea(point)
    
    def addSplit(self,x,y):
        point = Point(x,y)
        areas = self.getArea(point)
        
        if len(areas) == 0:
            return
        elif len(areas) == 1:
            area = areas[0]
            #Create points
            n = Point(point.x, area.points['nw'].y)
            w = Point(area.points['nw'].x, point.y)
            s = Point(point.x, area.points['se'].y)
            e = Point(area.points['se'].x, point.y)
            #Create Areas (nw,ne,se,sw,parent)
            area.subArea['nw'] = Area(area.points['nw'],n,point,w,area)
            area.subArea['ne'] = Area(n,area.points['ne'],e,point,area)
            area.subArea['se'] = Area(point,e,area.points['se'],s,area)
            area.subArea['sw'] = Area(w,point,s,area.points['sw'],area)
            #Fix connections
            point.neigh['n'] = n
            point.neigh['w'] = w
            point.neigh['s'] = s
            point.neigh['e'] = e
            n.neigh['s'] = point
            w.neigh['e'] = point
            s.neigh['n'] = point
            e.neigh['w'] = point
            (p1,p2) = area.points['nw'].getInterval('e')
            p1.neigh['e'] = n
            p2.neigh['w'] = n
            (p1,p2) = area.points['ne'].getInterval('s')
            p1.neigh['s'] = e
            p2.neigh['n'] = e
            (p1,p2) = area.points['se'].getInterval('w')
            p1.neigh['w'] = s
            p2.neigh['e'] = s
            (p1,p2) = area.points['sw'].getInterval('n')
            p1.neigh['n'] = w
            p2.neigh['s'] = w
        elif len(areas) == 2:
            if areas[0].points['nw'].x == point.x:
                n = areas[0].points['nw']
                w = Point(areas[1].points['nw'].x, point.y)
                s = areas[1].points['se']
                e = Point(areas[0].points['se'].x, point.y)
                #Create Areas (nw,ne,se,sw,parent)
                areas[0].subArea['ne'] = Area(n,areas[0].points['ne'],e,point,areas[0])
                areas[0].subArea['se'] = Area(point,e,areas[0].points['se'],s,areas[0])
                areas[1].subArea['nw'] = Area(areas[1].points['nw'],n,point,w,areas[1])
                areas[1].subArea['sw'] = Area(w,point,s,areas[1].points['sw'],areas[1])
                #Fix connections
                point.neigh['n'] = n
                point.neigh['w'] = w
                point.neigh['s'] = s
                point.neigh['e'] = e
                n.neigh['s'] = point
                w.neigh['e'] = point
                s.neigh['n'] = point
                e.neigh['w'] = point
                (p1,p2) = areas[0].points['nw'].getInterval('s')
                p1.neigh['s'] = point
                p2.neigh['n'] = point
                (p1,p2) = areas[0].points['se'].getInterval('n')
                p1.neigh['n'] = e
                p2.neigh['s'] = e
                (p1,p2) = areas[1].points['nw'].getInterval('s')
                p1.neigh['s'] = w
                p2.neigh['n'] = w
            elif areas[0].points['nw'].y == point.y:
                n = Point(point.x, areas[1].points['nw'].y)
                w = areas[0].points['nw']
                s = Point(point.x, areas[0].points['se'].y)
                e = areas[1].points['se']
                #Create Areas (nw,ne,se,sw,parent)
                areas[0].subArea['sw'] = Area(w,point,s,areas[0].points['sw'],areas[0])
                areas[0].subArea['se'] = Area(point,e,areas[0].points['se'],s,areas[0])
                areas[1].subArea['nw'] = Area(areas[1].points['nw'],n,point,w,areas[1])
                areas[1].subArea['ne'] = Area(n,areas[1].points['ne'],e,point,areas[1])
                #Fix connections
                point.neigh['n'] = n
                point.neigh['w'] = w
                point.neigh['s'] = s
                point.neigh['e'] = e
                n.neigh['s'] = point
                w.neigh['e'] = point
                s.neigh['n'] = point
                e.neigh['w'] = point
                (p1,p2) = areas[0].points['nw'].getInterval('e')
                p1.neigh['e'] = point
                p2.neigh['w'] = point
                (p1,p2) = areas[0].points['se'].getInterval('w')
                p1.neigh['w'] = s
                p2.neigh['e'] = s
                (p1,p2) = areas[1].points['nw'].getInterval('e')
                p1.neigh['e'] = n
                p2.neigh['w'] = n            
            elif areas[0].points['se'].x == point.x:
                n = areas[1].points['nw']
                w = Point(areas[0].points['nw'].x, point.y)
                s = areas[0].points['se']
                e = Point(areas[1].points['se'].x, point.y)
                #Create Areas (nw,ne,se,sw,parent)
                areas[1].subArea['ne'] = Area(n,areas[1].points['ne'],e,point,areas[1])
                areas[1].subArea['se'] = Area(point,e,areas[1].points['se'],s,areas[1])
                areas[0].subArea['nw'] = Area(areas[0].points['nw'],n,point,w,areas[0])
                areas[0].subArea['sw'] = Area(w,point,s,areas[0].points['sw'],areas[0])
                #Fix connections
                point.neigh['n'] = n
                point.neigh['w'] = w
                point.neigh['s'] = s
                point.neigh['e'] = e
                n.neigh['s'] = point
                w.neigh['e'] = point
                s.neigh['n'] = point
                e.neigh['w'] = point
                (p1,p2) = areas[1].points['nw'].getInterval('s')
                p1.neigh['s'] = point
                p2.neigh['n'] = point
                (p1,p2) = areas[1].points['se'].getInterval('n')
                p1.neigh['n'] = e
                p2.neigh['s'] = e
                (p1,p2) = areas[0].points['nw'].getInterval('s')
                p1.neigh['s'] = w
                p2.neigh['n'] = w
            elif areas[0].points['se'].y == point.y:
                n = Point(point.x, areas[0].points['nw'].y)
                w = areas[1].points['nw']
                s = Point(point.x, areas[1].points['se'].y)
                e = areas[0].points['se']
                #Create Areas (nw,ne,se,sw,parent)
                areas[1].subArea['sw'] = Area(w,point,s,areas[1].points['sw'],areas[1])
                areas[1].subArea['se'] = Area(point,e,areas[1].points['se'],s,areas[1])
                areas[0].subArea['nw'] = Area(areas[0].points['nw'],n,point,w,areas[0])
                areas[0].subArea['ne'] = Area(n,areas[0].points['ne'],e,point,areas[0])
                #Fix connections
                point.neigh['n'] = n
                point.neigh['w'] = w
                point.neigh['s'] = s
                point.neigh['e'] = e
                n.neigh['s'] = point
                w.neigh['e'] = point
                s.neigh['n'] = point
                e.neigh['w'] = point
                (p1,p2) = areas[1].points['nw'].getInterval('e')
                p1.neigh['e'] = point
                p2.neigh['w'] = point
                (p1,p2) = areas[1].points['se'].getInterval('w')
                p1.neigh['w'] = s
                p2.neigh['e'] = s
                (p1,p2) = areas[0].points['nw'].getInterval('e')
                p1.neigh['e'] = n
                p2.neigh['w'] = n            
        else:
            print 'Returned more that 2 Areas!'
        
class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        self.neigh = {}
    
    def getInterval(self,dir,point):
        if dir == 'n':
            if point.y >= self.neigh['n'].y:
                return (self,self.neigh['n'])
            else:
                return self.neigh['n'].getInterval(dir)
        elif dir == 'w':
            if point.x <= self.neigh['w'].x:
                return (self,self.neigh['w'])
            else:
                return self.neigh['w'].getInterval(dir)
        elif dir == 's':
            if point.y <= self.neigh['s'].y:
                return (self,self.neigh['s'])
            else:
                return self.neigh['s'].getInterval(dir)
        elif dir == 'e':
            if point.x >= self.neigh['e'].x:
                return (self,self.neigh['e'])
            else:
                return self.neigh['e'].getInterval(dir)


